#include "classical-problems.h"
#include <stdio.h>
#include <time.h>
#include <algorithm>

namespace pot {
bool Check(int i, int &c_mask, int &r_mask, int &l_mask) {
  return false;
}

// for 8-queen, permutation is a little faster
int Place8QueenNaive(int A[], int c_mask, int r_mask, int l_mask, int k) {
  if (k == 8) {
    // output or save result
    return 1;
  }
  
  int count = 0;
  for (int i = 0; i < 8; ++i) {
    int pos = 1 << i;
    int l_pos = 1 << (i + k); // [0 14]
    int r_pos = 1 << (i - k + 7); // [-7 7] -->[0 14]
    int exists = (c_mask & pos) | (l_mask & l_pos) | (r_mask & r_pos);
    if (exists == 0) {
      A[k] = i;      
      count += Place8QueenNaive(A, c_mask | pos, r_mask | r_pos, l_mask | l_pos, k + 1);
    }
  }
  return count;
}

int Place8QueenNaive(int A[]) {
  return Place8QueenNaive(A, 0, 0, 0, 0);
}

// only need diagonal test,
// this mask strategy can handle only up to 15-queen problem,
// however, it will be extremely slow for more than 15 queens
int Place8Queen(int A[], int r_mask, int l_mask, int k) {
  if (k == 8) return 1;

  int count = 0;
  for (int i = k; i < 8; ++i) {
    std::swap(A[i], A[k]);
            
    int l_pos = 1 << (A[k] + k); // [0 14]
    int r_pos = 1 << (A[k] - k + 7); // [-7 7] -->[0 14]
    int exists = (l_mask & l_pos) | (r_mask & r_pos);

    if (exists == 0) {
      count += Place8Queen(A, r_mask | r_pos, l_mask | l_pos, k + 1);
    }

    std::swap(A[i], A[k]);
  }
  
  return count;
}

void InitPlaces(int A[], int n) {
  for (int i = 0; i < n; ++i) A[i] = i;
}

int Place8Queen(int A[]) {
  InitPlaces(A, 8);

  return Place8Queen(A, 0, 0, 0);  
}

// simple check
bool Check(int A[], int k) { 
  for (int i = 0; i < k; ++i) {
    for (int j = i + 1; j <= k; ++j) {
      if (i - j == A[i] - A[j] ||
          j - i == A[i] - A[j]) 
        return false;
    }
  }
  return true;
}

int PlaceQueen(int A[], int n, int k) {
  // wastes time, if check here
  if (k == n) return 1;

  int count = 0;
  for (int i = k; i < n; ++i) {
    std::swap(A[i], A[k]);

    // pre-check saves time
    if (Check(A, k))
      count += PlaceQueen(A, n, k + 1);

    std::swap(A[i], A[k]);
  }
  return count;
}

int PlaceQueen(int A[], int n) {
  InitPlaces(A, n);

  return PlaceQueen(A, n, 0);
}

// use mask to check validity, need extra storage,
// up to 100x faster
int PlaceQueen(int A[], char mask[], int n, int k) {
  if (k == n)  return 1;

  int count = 0; 
  for (int i = k; i < n; ++i) {
    std::swap(A[i], A[k]);
    
    int l_pos = A[k] + k; // [0 14]
    int r_pos = A[k] - k + n - 1; // [-7 7] -->[0 14]
    
    char ltmp = mask[l_pos];
    char rtmp = mask[r_pos];
    
    int exists = (mask[l_pos] & 1) | (mask[r_pos] & 2);
    if (exists == 0) {
      mask[l_pos] |= 1;
      mask[r_pos] |= 2;
      count += PlaceQueen(A, mask, n, k + 1);
    }

    mask[l_pos] = ltmp;
    mask[r_pos] = rtmp;

    std::swap(A[i], A[k]);
  }
  return count;
}

int PlaceQueen(int A[], char mask[], int n) {
  InitPlaces(A, n);
  memset(mask, 0, 2 * n);
  return PlaceQueen(A, mask, n, 0);
}

void Place8QueenTest() {
  int A[15];
  char mask[30];
  int count = Place8QueenNaive(A);
  int count2 = Place8Queen(A);
  int count3 = PlaceQueen(A, 8);
  printf("%d, %d, %d\n", count, count2, count3);
  clock_t t0 = clock();
  for (int i = 4; i < 15; ++i) {
    PlaceQueen(A, i);
  }
  clock_t t1 = clock();
  for (int i = 4; i < 15; ++i) {
    PlaceQueen(A, mask, i);
  }
  clock_t t2 = clock();
  printf("%d, %d\n", t1-t0, t2 - t1);
}
} // pot
